1. Field of the Invention
The present invention relates to a method for automatic placement of a cell or a block in the layout of an integrated circuit by a gate array method or by a standard cell method, using a computer.
2. Description of the Prior Art
A semiconductor integrated circuit device has a configuration wherein cells or blocks with logic or memory functions are combined and arranged on a chip, and wiring is run among the respective I/O terminals of these cells and blocks so that a desired circuit operation is obtained.
FIG. 1 is a view showing a schematic configuration of a semiconductor integrated circuit chip which was designed using a conventional gate array method.
The chip comprises a region 51 wherein the cells are arranged, a region 52 wherein wiring is provided between the cells, and a region 53 wherein I/O circuits are provided on the periphery. The wiring region 52 is made up of a plurality of wiring layers. For example, the wiring in the horizontal and the vertical directions is conventionally distributed in different layers.
In this type of semiconductor integrated circuit device, when the layout of the cells and the like is determined by means of an automatic placement process using a computer the degree of complexity of the wiring must be made uniform, for example, the virtual wiring length must be minimized to simplify a subsequent wiring operation.
In the automatic placement process, normally, after the implementation of an initial placement phase in which the initial state of the placement is determined, the final placement is set by implementing a progressive placement refinement phase.
There are various procedures by which this progressive placement refinement phase can be implemented. Among them, the most simple method is a method of refining the placement which involves exchanging the position of a certain cell with that of another cell to create a new placement state. If this state is better than the original placement state, for example, if the virtual wiring length is shortened, the new placement state is adopted, if worse, a return is made to the original placement state, and these actions are repeated until an overall improvement is obtained. (M. Hanan, P. K. Wolff Sr., and B. J. Agule, "Some experimental results on placement techniques", Proceedings of the 13th Design Automation Conference, 1976, pp. 214 to 224).
This method leads to a drastic increase in the processing time required to improve the placement to satisfactorily meet the placement conditions as the result an increase in the number of cells. For this reason, if the number of cells is increased, the processing time is also increased, so there is the problem that implementation cannot be carried out.
Accordingly, it is necessary to achieve an increase in the processing speed to providing effective optimization within a finite processing time.
The following two methods are known as methods of solving the above-mentioned problems by refining the cell placement in parallel. Specifically, a method whereby the placement of like cells which are not directly connected is refined in parallel (first conventional method), and a method whereby placement is refined in parallel without this type of limitation--(second conventional method) have already been proposed ("A Parallel Processing Approach for Logic Module Placement", Kazuhiro UEDA, et al., IEEE Transactions on Computer-Aided Design, Vol. CAD-2, No.1, January 1983, pp.29-47).
However, with the former (first conventional method), in the case where cell exchange operations are implemented in parallel simultaneously, a means of selecting a pair of independent exchange cells which are not directly connected is introduced to eliminate refinement errors. For this reason, extra time is required with this method only for the time required for the computer to judge and qualify whether or not a pair of cells to be exchanged are mutually independent. Excessive processing time is necessary.
In addition, with this method a large number of repetitive operations are required until the refinement is completed, and it is difficult to proceed with an overall high-speed optimization because normally an extremely large number of pairs of exchange cells is present.
In addition, in the latter method (second conventional method), oscillation occurs when connected pairs of cells are exchanged because an operation to limit the number of pairs of independent exchange cells is not carried out.
For example, when placement of the cell shown as a circle in the upper right of FIG. 2A, and of the cell shown as a circle in the lower left of FIG. 2A, which is connected to this cell, is refined by different processors in parallel, the placement of this pair of cells is refined as shown in FIG. 2B because each processor tends to shorten the number of nets.
However, because each processor tends to further shorten the numbers of nets, the placement of this pair of cells is once again refined as in FIG. 2A. Because this type of refinement is repeated, oscillation (cells being alternately switched between two positions) occurs in the cell exchange. As a result, errors are produced in the respective refinement decisions and in the refinement decisions for the total chip.
There is also a method which differs from the above-described two placement refinement methods in parallel, whereby a region is simply divided to execute parallel operation. Because optimization occurs only within the divided region with this method, cell exchange between divided regions is not adequately provided.
The results of placement largely remain in the initial division, and it is difficult to optimize placement over the entire surface of the chip.
As outlined above, with the conventional cell placement refinement methods for automatic placement, there are the problems that the processing time required to improve the placement to satisfactorily meet the placement conditions drastically increases as the result an increase in the number of cells, refinement errors are produced, and it is difficult to finalize the process.
In particular, in the method whereby the chip region is simply divided to execute parallel operations, there are the problems that the number of divisions is limited by the number of processors which can utilized, cell exchange is not adequately provided between divided regions, the results of placement largely remain in the initial division, and it is difficult to optimize the placement over the entire surface of the chip.